#include "graphsupport/solve/facilitylocation/PrimalDualSolution.h"

#include <cmath>

#include "accumulsupport/AccumulSupport.h"

#include "graphsupport/graph/operation/MakeSymmOperation.h"

int PrimalDualSolution::createWitnessForCity( PrimDualSolvContext & scontext, int city )
{
	int facilitiesCount = scontext.fgraph.getFacilitiesCount();
	FacilitiesGraph::FacilityPriceType minPrice = scontext.fgraph.getInfEdge();
	int witness = -1;

	for ( int i = 0; i < facilitiesCount; i++ )
	{
		if ( scontext.fgraph.existsBiPartEdge( city, i ) )
		{
			FacilitiesGraph::FacilityPriceType roadPrice = scontext.getRoadPrice( city, i );
			FacilitiesGraph::FacilityPriceType fcltRemaind = scontext.fgraph.facilitiesPrices[i];
			fcltRemaind -= scontext.getPayedForFacility( i );
			FacilitiesGraph::FacilityPriceType totalPrice = roadPrice + fcltRemaind;

			if ( minPrice > totalPrice )
			{
				minPrice = totalPrice;
				witness = i;
			}
		}
	}

	if ( minPrice == scontext.fgraph.getInfEdge() )
	{
		return witness;
	}
	dbgassert( witness > -1 );

	scontext.setCityPays4total( city, minPrice );

	return witness;
}

bool PrimalDualSolution::createWitnessForAllCities( PrimDualSolvContext & scontext )
{
	int citiesCount = scontext.fgraph.getCitiesCount();
	for ( int city = 0; city < citiesCount; city++ )
	{
		int witness = createWitnessForCity( scontext, city );
		if ( witness == -1 )
		{
			return false;
		}
	}
	return true;
}

int PrimalDualSolution::findWitnessForCity( PrimDualSolvContext & scontext, int city )
{
	int facilitiesCount = scontext.fgraph.getFacilitiesCount();
	FacilitiesGraph::FacilityPriceType total = scontext.getCityPays4total( city );
	for ( int i = 0; i < facilitiesCount; i++ )
	{
		if ( scontext.fgraph.getFSEdge( city, i ) <= total + scontext.eps )
		{
			FacilitiesGraph::FacilityPriceType fPrice = scontext.fgraph.facilitiesPrices[i];
			FacilitiesGraph::FacilityPriceType fPayed = scontext.getPayedForFacility( i );
			if ( std::abs( fPrice - fPayed ) < scontext.eps )
			{
				return i;
			}
		}
	}
	return -1;
}

bool PrimalDualSolution::isSpecialEdge( PrimDualSolvContext & scontext, int city, int facility )
{
	return	scontext.fgraph.existsBiPartEdge( city, facility ) &&
			scontext.cityPays4fclt[city][facility] > scontext.eps;
}

bool PrimalDualSolution::isTightEdge( PrimDualSolvContext & scontext, int city, int facility )
{
	return scontext.getCityPays4road( city, facility ) >= scontext.getRoadPrice( city, facility ) - scontext.eps;
}

void PrimalDualSolution::computeSpecialEdgesSquareSubgraph( PrimDualSolvContext & scontext )
{
	int citiesCount = scontext.fgraph.getCitiesCount();
	int facilitiesCount = scontext.fgraph.getFacilitiesCount();
	Graph::AdjMatrixType adjMatr = scontext.specialSubgraph.getAdjacentMatrixArr();

	for ( int i = 0; i < facilitiesCount; i++ )
	{
		for ( int j = 0; j < facilitiesCount; j++ )
		{
			for ( int k = 0; k < citiesCount; k++ )
			{
				if ( isSpecialEdge( scontext, k, i ) && isSpecialEdge( scontext, k, j ) )
				{
					Graph::AdjCoefType curEdge = scontext.fgraph.getFSEdge( k, i );
					curEdge += scontext.fgraph.getFSEdge( k, j );
					adjMatr[i][j] = std::min( adjMatr[i][j], curEdge );
				}
			}
		}
	}

	MakeSymmOperation::makeSymm( scontext.specialSubgraph );
}

void PrimalDualSolution::computeMaximalIndependentSet( PrimDualSolvContext & scontext )
{
	int n = scontext.specialSubgraph.getVertexCount();
	std::fill( scontext.indepFacilities.begin(), scontext.indepFacilities.end(), false );
	for ( int i = 0; i < n; i++ )
	{
		if ( scontext.getPayedForFacility( i ) < scontext.fgraph.facilitiesPrices[i] - scontext.eps )
		{
			continue;
		}
		bool foundFromSet = false;
		for ( int j = 0; j < n; j++ )
		{
			if ( scontext.specialSubgraph.existsEdge( i, j ) && scontext.indepFacilities[j] )
			{
				foundFromSet = true;
				break;
			}
		}
		if ( !foundFromSet )
		{
			scontext.indepFacilities[i] = true;
		}
	}
}

void PrimalDualSolution::computeFacilityAssociations( PrimDualSolvContext & scontext )
{
	int citiesCount = scontext.fgraph.getCitiesCount();
	int facilitiesCount = scontext.fgraph.getFacilitiesCount();
	for ( int i = 0; i < citiesCount; i++ )
	{
		scontext.associatedFacility[i] = -1;

		for ( int fclt = 0; fclt < facilitiesCount; fclt++ )
		{
			if ( scontext.indepFacilities[fclt] && isSpecialEdge( scontext, i, fclt ) )
			{
				scontext.associatedFacility[i] = fclt;
				break;
			}
		}

		if ( scontext.associatedFacility[i] == -1 )
		{
			for ( int fclt = 0; fclt < facilitiesCount; fclt++ )
			{
				if ( scontext.indepFacilities[fclt] && isTightEdge( scontext, i, fclt ) )
				{
					scontext.associatedFacility[i] = fclt;
					break;
				}
			}
		}

		if ( scontext.associatedFacility[i] == -1 )
		{
			int witness = findWitnessForCity( scontext, i );
			if ( witness == -1 )
			{
				throw SolutionProcessException( "Unexpected value of a witness" );
			}
			for ( int fclt = 0; fclt < facilitiesCount; fclt++ )
			{
				if ( scontext.indepFacilities[fclt] )
				{
					if ( scontext.specialSubgraph.existsEdge( witness, fclt ) )
					{
						scontext.associatedFacility[i] = fclt;
						break;
					}
				}
			}
		}
	}
}

void PrimalDualSolution::openCheapestForNotExist( PrimDualSolvContext & scontext )
{
	int citiesCount = scontext.fgraph.getCitiesCount();
	int facilitiesCount = scontext.fgraph.getFacilitiesCount();

	for ( int i = 0; i < citiesCount; i++ )
	{
		int witness = scontext.associatedFacility[i];
		if ( scontext.fgraph.existsBiPartEdge( i, witness ) )
		{
			continue;
		}
		FacilitiesGraph::FacilityPriceType cheapest = scontext.fgraph.getInfEdge();
		for ( int j = 0; j < facilitiesCount; j++ )
		{
			if ( cheapest > scontext.fgraph.facilitiesPrices[j] + scontext.fgraph.getFSEdge( i, j ) )
			{
				cheapest = scontext.fgraph.facilitiesPrices[j] + scontext.fgraph.getFSEdge( i, j );
				scontext.associatedFacility[i] = j;
			}
		}
		witness = scontext.associatedFacility[i];
		scontext.indepFacilities[witness] = true;
	}
}
